package 队列;

public class ArrayQueue {
    //定义队列结构

    //使用数组来存储队列
    private Object[] elements;
    //定义队列大小
    private int size;
    //定义队列初始容量
    private int DEFAULT_SIZE = 10;
    //定义一个容量最大值
    private int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //定义一个头指针
    private int head;
    //定义一个尾指针
    private int tail;

    public ArrayQueue() {
        elements = new Object[DEFAULT_SIZE];
        //初始化首尾指针
        this.initPoint(0, 0);
    }

    private void initPoint(int head, int tail) {
        this.head = head;
        this.tail = tail;
    }

    public ArrayQueue(int capcity) {
        if (capcity <= 0) {
            throw new RuntimeException("数组初始容量不能小于等于0");
        }
        elements = new Object[capcity];
        this.initPoint(0, 0);
    }

    //入队列（支持动态扩容）
    public boolean enqueue(Object element) {
        //校验队列容量是否够用
        ensureSizeHelper();
        elements[tail++] = element;
        size++;
        return true;
    }

    //出队列
    public Object dequeue(){
        if (head==tail){
            return null;
        }
        Object object = elements[head++];
        size--;
        return object;
    }

    //动态扩容机制
    //1.判断队列容量是否够用
    private void ensureSizeHelper() {
        //尾指针已经越过队列尾部
        if (tail == elements.length) {
            if (size < elements.length) {
                if (head == 0) {
                    //扩容操作
                    grow(size);
                } else {
                    //数据搬移操作
                    for (int i = head; i < tail; i++) {
                        elements[i - head] = elements[i];
                    }
                    initPoint(0, tail - head);
                }
            }
        }
    }


    //扩容方法
    private void grow(int oldSize) {
        //扩容1.5倍
        int newSize = oldSize + (oldSize >> 1);
        if (newSize - oldSize <= 0) {
            newSize = DEFAULT_SIZE;
        }
        if (newSize - MAX_ARRAY_SIZE > 0) {
            //数组移动
            newSize = capcityFinal(newSize);
        }
    }

    private int capcityFinal(int newSize) {
        return (newSize > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE - 8 : newSize;
    }
}
